package com.xiyou.week05.binarySearch;

/**
 * 1482. 制作 m 束花所需的最少天数
 *
 * @ClassName：MinDays
 * @Author：西柚
 * @Date：2022/1/28 11:51 上午
 * @Versiion：1.0
 */
public class MinDays {

    /**
     * 输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
     * 输出：3
     * 解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
     * 现在需要制作 3 束花，每束只需要 1 朵。
     * 1 天后：[x, _, _, _, _]   // 只能制作 1 束花
     * 2 天后：[x, _, _, _, x]   // 只能制作 2 束花
     * 3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3
     * <p>
     * 链接：https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets
     *
     * @param bloomDay
     * @param m
     * @param k
     * @return
     */
    public int minDays(int[] bloomDay, int m, int k) {
        int latestBloom = 0;
        for (int bloom : bloomDay) {
            latestBloom = Math.max(latestBloom, bloom);
        }
        int left = 0, right = latestBloom + 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (validateOnDay(bloomDay, m, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (right == latestBloom + 1) {
            return -1;
        }
        return right;
    }

    private boolean validateOnDay(int[] bloomDay, int m, int k, int now) {
        int bouquet = 0;
        int consecutive = 0;
        for (int bloom : bloomDay) {
            if (bloom <= now) {
                consecutive++;
                if (consecutive == k) {
                    bouquet++;
                    consecutive = 0;
                }
            } else {
                consecutive = 0;
            }
        }
        return bouquet >= m;
    }

    public static void main(String[] args) {
        int[] bloomDay = {1, 10, 3, 10, 2};
        int m = 3;
        int k = 1;
        MinDays minDays = new MinDays();
        System.out.println(minDays.minDays(bloomDay, m, k));
    }

}
